package practice1_100;

import java.util.Arrays;

public class Practice63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int height=obstacleGrid.length;
        int weight=obstacleGrid[0].length;

        if(obstacleGrid[height-1][weight-1]==1||obstacleGrid[0][0]==1) return 0;//考虑极端情况，出口进口堵死

        int[][] dpTable=new int[height][weight];//弄出来dp数组
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < weight; j++) {
                dpTable[i][j]=-1;
            }
        }
//        Arrays.fill(dpTable,-1);
        dpTable[0][0]=1;//设置出口的路径为唯一一条，结果就是1，
       return dp(obstacleGrid,dpTable,height-1,weight-1);//调用递归的方法
    }

    private int  dp(int[][] obstacleGrid, int[][] dpTable, int m, int n) {
        //如果越界就返回0，baseCase
        if(m==0&&n==0) return 1;
        if(m<0||n<0) return 0;

        if (obstacleGrid[m][n]==1) dpTable[m][n]=0;//原数组中这个路上有障碍，直接设置为0，
        if(dpTable[m][n]!=-1) return dpTable[m][n];//dpTable作为记录，先查表，若不为-1，代表这个地方已经算出结果，直接返回
        if(obstacleGrid[m][n]!=1)//其实这句可以不要了
            dpTable[m][n]=dp(obstacleGrid,dpTable,m-1,n)+dp(obstacleGrid,dpTable,m,n-1);//先将dpTable存起来
        return dpTable[m][n];
    }

    public static void main(String[] args) {
        int[][] b=new int[20000][20000];
//        for (int i = 0; i < b.length; i++) {
//            for (int j = 0; j < b[0].length; j++) {
//
//            }
//        }
        int [][] c=new int[][]{{0,1,0,0,0},{0,0,0,0,0},{1,0,0,0,0}};
        int a=new Practice63().uniquePathsWithObstacles(c);
        System.out.println(a);
        int d=new Practice63().uniquePathsWithObstacles1(b);
        System.out.println(d);
    }

    //正向解法，从下至上
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int column=obstacleGrid[0].length;
        int[][] dpTable=new int[row][column];

        for (int i = 0; i < row; i++) {
            if(obstacleGrid[i][0]==1) break;
            dpTable[i][0]=1;
        }
        for (int i = 0; i < column; i++) {
            if(obstacleGrid[0][i]==1) break;
            dpTable[0][i]=1;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < column; j++) {
                if(obstacleGrid[i][j]==1) dpTable[i][j]=0;
                dpTable[i][j]=dpTable[i-1][j]+dpTable[i][j-1];
            }
        }
        return dpTable[row-1][column-1];
    }
}
